package com.stanley.alogrithm.dynamic;

import java.util.ArrayList;
import java.util.List;

public class LongestCommonString {

    private List<Character> maxConjointChars = new ArrayList<Character>();
    private String maxStr = null;



    public static void main(String[] args) {
        //String str1 = "1AB2345CD";
        //String str2 = "XXX1AB";
        String str1 = "1AB2345CD";
        String str2 = "12345EF";
        LongestCommonString lcs = new LongestCommonString();
        String common = lcs.LCS(str1, str2);
        System.out.println("Common: " + common);
    }
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int len1 = str1.length();
        int len2 = str2.length();
        int leftDelta=0, end=0;
        String longStr, shortStr;
        if(len1 >= len2) {
            // str1 不动
            longStr = str1;
            shortStr = str2;
        } else {
            // str2 不动
            longStr = str2;
            shortStr = str1;
        }
        end = longStr.length() - 1;
        int maxCommonCount = 0;
        for (leftDelta = -(shortStr.length() - 1); leftDelta <= end; leftDelta++) {
            int commonCount = 0;
            StringBuffer sb = new StringBuffer();
            StringBuilder sb2;

            int right = Math.min(end, shortStr.length() - 1 + leftDelta);
            int left = Math.max(0, leftDelta);
            System.out.println("leftDelta= " + leftDelta + ", right=" + right);
            for (int i = left; i <= right; i++) {
                if(longStr.charAt(i) == shortStr.charAt( i - leftDelta)) {
                    commonCount++;
                    sb.append(longStr.charAt(i));
                } else {
                    if(commonCount > maxCommonCount) {
                        maxStr = sb.toString();
                        maxCommonCount = commonCount;
                    }
                    commonCount = 0;
                    sb = new StringBuffer();
                }
            }
            if(commonCount > maxCommonCount) {
                maxStr = sb.toString();
                maxCommonCount = commonCount;
            }
        }

        return maxStr;
    }

//    private int findLCS(char[] chars1, char[] chars2, int start1, int start2, int maxLen) {
//        int p1 = start1 + maxLen, p2 = start2 + maxLen;
//        if (chars1[p1 + 1] == chars2[p2 + 1]) {
//            maxConjointChars.add(chars1[p1 + 1]);
//            p1++;
//            p2++;
//        } else {
//
//        }
//    }
//
//    private ProbeInfo findNextCommonChar(char[] chars1, char[] chars2, ProbeInfo current) {
//        int index1 =  current.starIndex1 + 1;
//        int index2 = current.startIndex2 + 1;
//        while (index1 < chars1.length && index2 < chars2.length) {
//            if(chars1[index1] == chars2[index2]){
//
//            }
//            return null;
//        }
//
//    }


}
